#include "Table.h"
#include "Util.h"

unordered_map<string, unordered_set<string>> FirstSet;   // 存放FIRST集合
unordered_map<string, unordered_set<string>> FirstSetBeta;  // 存放β的first
unordered_map<string, unordered_set<string>> FollowSet;
unordered_map<string, vector<string>> production_map; // 存放产生式
Production *productionsArray[GRAMMAR_SIZE]; // 产生式数组
unordered_set<string> VnSet;
unordered_set<string> VtSet;
map<string, int> predictionTable;
string start = "Program";

void getFirst(const string &ch) {
    vector<string> ch_production = production_map[ch]; // 该符号的产生式
    unordered_set<string> set = FirstSet[ch];
    // ch为终结符
    if (VtSet.count(ch)) {
        set.insert(ch);
        FirstSet[ch] = set;
        return;
    }
    // ch为非终结符
    for (const string &str: ch_production) {
        istringstream iss(str);
        vector<string> temp2((istream_iterator<string>(iss)), istream_iterator<string>());
        int i = 0;
        while (i < temp2.size()) {
            string tn = temp2[i];
            // 递归
            getFirst(tn);
            unordered_set<string> tvSet = FirstSet[tn];
            // 将其first集加入左部
            for (const string &tmp: tvSet) {
                if (tmp != "$") {
                    set.insert(tmp);
                }
            }
            // 若包含空串处理下一个符号
            if (tvSet.count("$")) {
                i++;
            } else {
                break;
            }
        }
        if (i == temp2.size()) { // 所有的符号的first集合中均有$符号
            set.insert("$");
        }
    }
    FirstSet[ch] = set;
}

void getFirstOfBeta(const string &s) {
    unordered_set<string> set = FirstSetBeta[s];
    istringstream iss(s);
    vector<string> temp3((istream_iterator<string>(iss)), istream_iterator<string>());
    int i = 0;
    while (i < temp3.size()) {
        string tn = temp3[i];
        if (!FirstSet.count(tn)) {
            getFirst(tn);
        }
        unordered_set<string> tvSet = FirstSet[tn];
        // 将其非空first集加入左部
        for (const string &tmp: tvSet) {
            if (tmp != "$") {
                set.insert(tmp);
            }
        }
        // 若包含空串处理下一个符号
        if (tvSet.count("$")) {
            i++;
        } else {
            break;
        }
        // 到了尾部，即所有符号的first集都包含空串，把空串加入
        if (i == temp3.size()) {
            set.insert("$");
        }
    }
    FirstSetBeta[s] = set;
}

void First() {
    // 遍历非终结符
    for (const string &vn: VnSet) {
        getFirst(vn);
    }

    for (const string &vn: VnSet) {
        vector<string> l = production_map[vn];
        for (const string &s: l) {
            getFirstOfBeta(s);
        }
    }
}

void Follow() {
    // 初始化所有非终结符的Follow集为空集
    for (const string &vn: VnSet) {
        FollowSet[vn] = unordered_set<string>();
    }
    // 将#加入到文法开始符号program的Follow集中
    FollowSet[start].insert("#");
    bool changed = true;
    while (changed) {
        changed = false;
        // 循环文法集
        for (const auto &[left_vn, right_symbol_list]: production_map) {
            for (const string &rhs: right_symbol_list) {
                istringstream iss(rhs);
                vector<string> symbols((istream_iterator<string>(iss)), istream_iterator<string>());
                for (size_t i = 0; i < symbols.size(); ++i) {
                    const string &B = symbols[i];
                    if (VnSet.count(B)) { // 如果是非终结符
                        unordered_set<string> &followB = FollowSet[B];
                        size_t j = i + 1;
                        while (j < symbols.size()) {
                            const string &beta = symbols[j];
                            if (!VnSet.count(symbols[j])) {
                                if (followB.insert(symbols[j]).second) {
                                    changed = true;
                                }
                            }
                            const unordered_set<string> &firstOfBeta = FirstSet[beta];
                            bool containsEpsilon = firstOfBeta.count("$");
                            for (const string &terminal: firstOfBeta) {
                                if (terminal != "$") {
                                    if (followB.insert(terminal).second) {
                                        changed = true;
                                    }
                                }
                            }
                            if (containsEpsilon) {
                                ++j;
                            } else {
                                break;
                            }
                        }
                        if (j == symbols.size()) {
                            const unordered_set<string> &followA = FollowSet[left_vn];
                            for (const string &terminal: followA) {
                                if (followB.insert(terminal).second) {
                                    changed = true;
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

//提取分析终结符和非终结符
void processSymbolsToVnSetAndVtSet() {
    vector<string> grammarStr;
    //size_t length = sizeof(productionsArray) / sizeof(productionsArray[0]);
    for (auto &i: productionsArray) {
        grammarStr.push_back(i->production_string);
    }
    // 将产生式存储到production
    for (const string &str: grammarStr) {
        // 将产生式按照 -> 分开
        string left = str.substr(0, str.find("->"));
        string right = str.substr(str.find("->") + 2);
        left = left.substr(left.find_first_not_of(' '), left.find_last_not_of(' ') + 1);
        right = right.substr(right.find_first_not_of(' '), right.find_last_not_of(' ') + 1);
        // 如果产生式里已经有left，先取出原来的值
        vector<string> list = production_map[left];
        list.push_back(right);
        production_map[left] = list;
        VnSet.insert(left); // 在产生式左边的一定是非终结符
    }
    // 寻找终结符
    for (const string &vn: VnSet) {
        for (const string &prod: production_map[vn]) {
            istringstream iss(prod);
            string token;
            while (iss >> token) {
                if (!VnSet.count(token)) {
                    VtSet.insert(token);
                }
            }
        }
    }
}

//文法读取
void initProductions(const char *filename) {
    ifstream file(filename);
    if (!file.is_open()) {
        cerr << "Error opening grammar file" << endl;
        return;
    }

    string line;
    int index = 0; // 产生式索引
    while (getline(file, line)) {
        if (line.empty()) {
            continue; // 跳过空行
        }

        size_t arrowPos = line.find("->");
        if (arrowPos == string::npos) {
            cerr << "Invalid production_map rule: " << line << endl;
            continue;
        }

        string left = line.substr(0, arrowPos - 1); // 获取产生式左部
        string right = line.substr(arrowPos + 2); // 获取产生式右部

        istringstream iss(right);
        vector<string> rightSymbols;
        string symbol;
        while (iss >> symbol) {
            rightSymbols.push_back(symbol);
        }
        productionsArray[index++] = new Production(left, rightSymbols, line); // 创建产生式对象并添加到数组中
    }
    file.close(); // 关闭文件
    processSymbolsToVnSetAndVtSet();
}

void outputVnVt() {
    cout << "================= Terminal =================" << endl;
    for (const string &ch: VtSet) {
        cout << ch << endl;
    }

    cout << "================= Non-Terminal =================" << endl;
    for (const string &ch: VnSet) {
        cout << ch << endl;
    }

    cout << "================= FIRST Set =================" << endl;
    for (const string &c: VnSet) {
        const unordered_set<string> &set = FirstSet[c];
        cout << c << " : ";
        for (const string &var: set) {
            cout << var << " ";
        }
        cout << endl;
    }
    cout << endl;

    cout << "================= FOLLOW Set =================" << endl;
    for (const string &c: VnSet) {
        const unordered_set<string> &set = FollowSet[c];
        cout << c << " : ";
        for (const string &var: set) {
            cout << var << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// 生成预测表的键
string getMapKey(const string &terminal, const string &nonTerminal) {
    return "{x: " + terminal + "  y: " + nonTerminal + "}";
}

// 计算右边符号串的整体FIRST集
unordered_set<string> computeFirstToRightsSymbols(const vector<string> &symbols) {
    unordered_set<string> result;
    for (const auto &symbol: symbols) {//分析所有符号
        if (VtSet.count(symbol)) {//如果是终结符，插入到结果中，直接返回
            result.insert(symbol);
            return result;
        }
        if (FirstSet.find(symbol) != FirstSet.end()) {//如果不是从头开始数的最后一个非终结符且first集含$，继续，否则断开
            const auto &firstSet = FirstSet[symbol];//找到当前非终结符的first集插入至result
            result.insert(firstSet.begin(), firstSet.end());
            if (firstSet.count("$") == 0) {//如果first集不含$，断开
                return result;
            }
        } else {
            cout << "Non-terminal " << symbol << " not found in FirstSet" << endl;
            break;
        }
    }
    result.erase("$");
    return result;
}

void setPrediction() {
    for (int i = 0; i < GRAMMAR_SIZE; ++i) {
        const Production &production = *productionsArray[i];
        if (production.right_string[0] == "$") {
            continue;   // 跳过类似于 value' -> $ 的文法
        }
        try {
            unordered_set<string> firstSet = computeFirstToRightsSymbols(production.right_string);
            for (const auto &terminal: firstSet) {
                if (terminal == "$") {
                    const auto &followSet = FollowSet.at(production.left_symbol);
                    for (const auto &followTerminal: followSet) {
                        predictionTable[getMapKey(followTerminal, production.left_symbol)] = i;
                    }
                } else {
                    predictionTable[getMapKey(terminal, production.left_symbol)] = i;
                }
            }
        } catch (const out_of_range &e) {
            cout << "First set does not contain key: " << production.right_string[0] << endl;
        }
    }
    for (int i = 0; i < GRAMMAR_SIZE; ++i) {
        const Production &production = *productionsArray[i];
        if (production.right_string[0] == "$") {
            const auto &followSet = FollowSet.at(production.left_symbol);
            for (const auto &followTerminal: followSet) {
                predictionTable[getMapKey(followTerminal, production.left_symbol)] = i;
            }
        }
    }
}






